package pers.qianyu.month_202103.date_20210306.qixinan;

import org.junit.*;

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 最大牛奶桶数
     *
     * @param grass int整型一维数组 吃的草的捆数
     * @param milk  int整型一维数组 产的牛奶桶数
     * @return int整型
     */
    public int MaxMilk(int[] grass, int[] milk) {
        int n = grass.length;
        if (n == 0) return 0;
        map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, new HashSet<>());
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isFight(grass, milk, i, j)) {
                    map.get(i).add(j);
                    map.get(j).add(i);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            HashSet<Integer> invalid = new HashSet<>(map.get(i));
            invalid.add(i);
            recur(milk, milk[i], invalid);
        }
        return max;
    }

    private void recur(int[] milk, int sum, Set<Integer> invalid) {
        max = Math.max(max, sum);
        int n = milk.length;
        for (int i = 0; i < n; i++) {
            if (!invalid.contains(i)) {
                HashSet<Integer> s1 = new HashSet<>(invalid);
                s1.add(i);
                s1.addAll(map.get(i));
                recur(milk, sum + milk[i], s1);
            }
        }
    }

    private int max = 0;
    private HashMap<Integer, Set<Integer>> map;

    private boolean isFight(int[] grass, int[] milk, int i, int j) {
        return grass[i] > grass[j] && milk[i] < milk[j] || grass[i] < grass[j] && milk[i] > milk[j];
    }

    @Test
    public void test1() {
        int res = new Solution().MaxMilk(new int[]{5, 5, 5, 5, 5}, new int[]{1, 5, 3, 4, 2});
        Assert.assertEquals(15, res);
    }

    @Test
    public void test2() {
        int res = new Solution().MaxMilk(new int[]{2, 3, 4, 5, 6}, new int[]{2, 4, 7, 9, 12});
        Assert.assertEquals(34, res);
    }

    @Test
    public void test3() {
        int res = new Solution().MaxMilk(new int[]{1, 3, 2, 7, 5}, new int[]{3, 3, 3, 3, 3});
        Assert.assertEquals(15, res);
    }

    @Test
    public void test4() {
        int res = new Solution().MaxMilk(new int[]{5, 5, 5, 5, 5}, new int[]{3, 3, 3, 3, 3});
        Assert.assertEquals(15, res);
    }

    @Test
    public void test5() {
        int res = new Solution().MaxMilk(new int[]{3, 5, 8, 2}, new int[]{2, 3, 5, 7});
        Assert.assertEquals(10, res);
    }
}